#include<iostream>
#include<string>
#include<vector>

using namespace std;

class Solution{
    public:
    int ans1(vector<int>& nums){
        int len = nums.size();
        int pre = 0, maxAns = nums[0];
        for(int i = 0; i != len; i++){
            pre = max(pre + nums[i], nums[i]);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};

void test(){
    Solution s;
    vector<int> nums = {-2,1,-3,4,-1,2,1,-5,4};

    int ret = s.ans1(nums);
    cout << ret << endl;
}

int main(void){
    test();

    return 0;
}